package 对称二叉树;

import java.util.*;

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 使用迭代法
        // 核心思想同递归法一样，都是不断的将p的左孩子和q的右孩子比较，p的右孩子和q的左孩子进行比较
        if(root == null)
            return true;
        return checkSymmetric(root.left, root.right);
    }

    private boolean checkSymmetric(TreeNode p, TreeNode q) {
        // 使用LinkedList类是因为该类支持存入null值, ArrayDeque类是以null值作为队列的结尾，所以不能存放null值
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);
        while (!queue.isEmpty()){
            // 从队列中取出两个待比较节点
            p = queue.poll();
            q = queue.poll();
            // 如果两个均为null,说明对称
            if(p == null && q == null )
                continue;
            // 如果其中一个为null，另一个不为null。或者两个节点值不相等则返回false
            if(p == null || q == null || p.val != q.val)
                return false;
            // 将p的左孩子和q的右孩子入队
            queue.offer(p.left);
            queue.offer(q.right);
            // 将p的右孩子吉尔q的左孩子入队
            queue.offer(p.right);
            queue.offer(q.left);
        }
        return true;
    }
}
